package offerbook;


//TODO  O(logN)解法

public class Code09_Fibonacci {

    /**
     *  迭代次数是完全二叉树的节点数 2^n -1
     *  时间O(2^N)
     */
    public static int fibonacci1(int n){
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        return fibonacci1(n-1)+fibonacci1(n-2);
    }

    //o(N)
    public static int fibonacci2(int n){
        if(n==0){
            return 0;
        }
        if(n==1 || n==2){
            return 1;
        }
        int f1 = 1;
        int f2 = 1;
        int f3 = 2;
        for (int i = 3; i <=n; i++) {
            f3 = f1 + f2;
            f1 = f2;
            f2 = f3;
        }
        return f3;
    }

    //O(logN)


}
